package pen_exam.smallredbook_2024_03_24;

public class Code_Tuiguang {
    public static int Tuiguang(int[] arr,int x){
        return process(arr,x,0,0);
    }
    //map《index,sum》
    public static int process(int[] arr,int x,int index,int sum){
        if(index == arr.length){
          return   sum == x ? 0 : Integer.MAX_VALUE;
        }
        int p1 = process(arr,x,index + 1,sum);
        int p2 = process(arr,x,index + 1,sum + (arr[index] >> 1));
        if(p2 != Integer.MAX_VALUE){
            p2 += 1;
        }
        int p3 = process(arr,x,index + 1,sum + arr[index]);
        if(p3 != Integer.MAX_VALUE){
            p3 += 1;
        }
        return Math.min(p1,Math.min(p2,p3));
    }
    public static int dp(int[] arr,int x){
        int n = arr.length;
        int[][] dp = new int[n + 1][x + 1];
        for (int i = 0; i < x; i++) {
            dp[n][i] = Integer.MAX_VALUE;
        }
        for(int index = n - 1;index >= 0;index--){
            for(int sum = 0;sum <= x;sum++){
                int p1 = dp[index + 1][sum];
                int p2 = Integer.MAX_VALUE;
                int p3 = Integer.MAX_VALUE;
                if(sum + (arr[index] >> 1) <= x){
                     p2 = dp[index + 1][sum + (arr[index] >> 1)];
                    if(p2 != Integer.MAX_VALUE){
                        p2 += 1;
                    }
                }
                if(sum + (arr[index]) <= x){
                     p3 = dp[index + 1][sum + arr[index]];
                    if(p3 != Integer.MAX_VALUE){
                        p3 += 1;
                    }
                }

                dp[index][sum] = Math.min(p1,Math.min(p2,p3));
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,10};
        System.out.println(dp(arr,8));
    }
}
